import java.util.ArrayList;
import java.util.List;

/**
 * 1781. 所有子字符串美丽值之和
 * https://leetcode-cn.com/problems/sum-of-beauty-of-all-substrings/
 */
public class Solutions_1781 {
    public static void main(String[] args) {
        String s1 = "aabcb";  // output: 5
//        解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1
        String s2 = "aabcbaa";  // output: 17

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);

        for (String input : inputs) {
            int result = beautySum(input);
            System.out.println(result);
        }
    }

    /**
     * 暴力法
     * 双重 for 循环解决
     */
    public static int beautySum(String s) {
        char[] arr = s.toCharArray();
        int len = arr.length;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int[] counts = new int[26];
            for (int j = i; j < len; j++) {
                counts[arr[j] - 'a'] ++;
                // 3 个字符比较最大、最小出现次数才有意义
                if (j - i + 1 >= 3) {
                    int maxCnt = Integer.MIN_VALUE;
                    int minCnt = Integer.MAX_VALUE;
                    for (int k = 0; k < 26; k++) {
                        if (counts[k] > 0) {
                            maxCnt = Math.max(maxCnt, counts[k]);
                            minCnt = Math.min(minCnt, counts[k]);
                        }
                    }
                    // 美丽值：最大出现次数 - 最少出现次数
                    res += maxCnt - minCnt;
                }
            }
        }
        return res;
    }
}
